{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #字母迷宫"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #backtracking #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #回溯 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: wordPuzzle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #字母迷宫"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>字母迷宫游戏初始界面记作 <code>m x n</code> 二维字符串数组 <code>grid</code>，请判断玩家是否能在 <code>grid</code> 中找到目标单词 <code>target</code>。<br />\n",
    "注意：寻找单词时 <strong>必须</strong> 按照字母顺序，通过水平或垂直方向相邻的单元格内的字母构成，同时，同一个单元格内的字母&nbsp;<strong>不允许被重复使用&nbsp;</strong>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/11/04/word2.jpg\" /></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[\"A\",\"B\",\"C\",\"E\"],[\"S\",\"F\",\"C\",\"S\"],[\"A\",\"D\",\"E\",\"E\"]], target = \"ABCCED\"\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[\"A\",\"B\",\"C\",\"E\"],[\"S\",\"F\",\"C\",\"S\"],[\"A\",\"D\",\"E\",\"E\"]], target = \"SEE\"\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[\"A\",\"B\",\"C\",\"E\"],[\"S\",\"F\",\"C\",\"S\"],[\"A\",\"D\",\"E\",\"E\"]], target = \"ABCB\"\n",
    "<strong>输出：</strong>false\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == grid.length</code></li>\n",
    "\t<li><code>n = grid[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 6</code></li>\n",
    "\t<li><code>1 &lt;= target.length &lt;= 15</code></li>\n",
    "\t<li><code>grid</code> 和 <code>target</code> 仅由大小写英文字母组成</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>注意：</strong>本题与主站 79 题相同：<a href=\"https://leetcode-cn.com/problems/word-search/\">https://leetcode-cn.com/problems/word-search/</a></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [ju-zhen-zhong-de-lu-jing-lcof](https://leetcode.cn/problems/ju-zhen-zhong-de-lu-jing-lcof/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [ju-zhen-zhong-de-lu-jing-lcof](https://leetcode.cn/problems/ju-zhen-zhong-de-lu-jing-lcof/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[\"A\",\"B\",\"C\",\"E\"],[\"S\",\"F\",\"C\",\"S\"],[\"A\",\"D\",\"E\",\"E\"]]\\n\"ABCCED\"', '[[\"A\",\"B\",\"C\",\"E\"],[\"S\",\"F\",\"C\",\"S\"],[\"A\",\"D\",\"E\",\"E\"]]\\n\"SEE\"', '[[\"A\",\"B\",\"C\",\"E\"],[\"S\",\"F\",\"C\",\"S\"],[\"A\",\"D\",\"E\",\"E\"]]\\n\"ABCB\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPuzzle(self, grid: List[List[str]], target: str) -> bool:\n",
    "        res = []\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == target[0]:\n",
    "                    res.append([i,j,0,[1,1,1,1]])\n",
    "        for _ in range(len(res)):\n",
    "            stack = [res.pop()]\n",
    "            i,j,index,dirs = stack[-1]\n",
    "            grid[i][j] = \"*\"\n",
    "            while stack:\n",
    "                i,j,index,dirs = stack[-1]\n",
    "                if index == len(target)-1:\n",
    "                    return True\n",
    "                for dir,(x,y) in enumerate([(i-1,j),(i+1,j),(i,j-1),(i,j+1)]):\n",
    "                    if dirs[dir]:\n",
    "                        if 0<=x<len(grid) and 0<=y<len(grid[0]) and grid[x][y]==target[index+1]:\n",
    "                            stack[-1][3][dir]=0\n",
    "                            stack.append([x,y,index+1,[1,1,1,1]])\n",
    "                            grid[x][y] = \"*\"\n",
    "                            break\n",
    "                else:\n",
    "                    grid[i][j]=target[index]\n",
    "                    stack.pop()\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPuzzle(self, grid: List[List[str]], target: str) -> bool:\n",
    "        visited = [[False for i in range(0,len(grid[0]))] \\\n",
    "            for j in range(0,len(grid))]\n",
    "        b = False\n",
    "        for i in range(0,len(grid)) :\n",
    "            for j in range(0,len(grid[i])) :\n",
    "                if grid[i][j]==target[0] :\n",
    "                    #print(i,j)\n",
    "                    b1 = self.hasPath(grid,target,i,j,0,visited)\n",
    "                    if b1 :\n",
    "                        b = b1\n",
    "        return b\n",
    "    def hasPath(self, grid: List[List[str]],target: str,i: int,j: int,k: int,visited: List[List[str]]) -> bool:\n",
    "       if k>=len(target) : return True\n",
    "       if i<0 or i>=len(grid) or j<0 or j>=len(grid[0]) :\n",
    "           return False\n",
    "       if visited[i][j] == 1 :  return False\n",
    "       b = True\n",
    "       #print(i,j,k,grid[i][j],target[k],visited)\n",
    "       if grid[i][j]!=target[k] and visited[i][j]==0: return False\n",
    "       if grid[i][j]==target[k] and visited[i][j]==0:\n",
    "           visited[i][j] = True\n",
    "           b = self.hasPath(grid,target,i-1,j,k+1,visited) or \\\n",
    "               self.hasPath(grid,target,i+1,j,k+1,visited) or \\\n",
    "               self.hasPath(grid,target,i,j-1,k+1,visited) or \\\n",
    "               self.hasPath(grid,target,i,j+1,k+1,visited)\n",
    "           #print(i,j,k,b)\n",
    "       if b==False :\n",
    "           visited[i][j] = False\n",
    "           \n",
    "       return b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPuzzle(self, grid: List[List[str]], target: str) -> bool:\n",
    "        # 说白了本题也是暴力搜索，先暴力搜索起点，再从不同起点遍历搜索四个方向\n",
    "        # 从第一行从左往右遍历，因此遵循下，右，上，左的方向\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                result = self.backtracking(grid, i, j, target, 0)\n",
    "                if result: return True\n",
    "        return False\n",
    "        \n",
    "    \n",
    "    def backtracking(self, grid, i, j, target, w): # w用于记录搜索到target的第几个字符\n",
    "\n",
    "        # 终止条件\n",
    "        if w >= len(target) : # 递归到末尾了\n",
    "            return True\n",
    "        \n",
    "        # 这两个的顺序也很重要，当字符串已经匹配完时，即便超界，也应该先返回True\n",
    "        if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]): return False\n",
    "        \n",
    "        # 单层递归条件\n",
    "        if grid[i][j] == target[w]:\n",
    "            # 记得将原来的上一个格子标记为'', 不然会走回头路\n",
    "            # 比如用这个例子测试：[[\"A\",\"B\",\"C\",\"E\"],[\"S\",\"F\",\"C\",\"S\"],[\"A\",\"D\",\"E\",\"E\"]]\n",
    "            # \"ABCB\"\n",
    "            grid[i][j] = '.'\n",
    "            res = self.backtracking(grid, i + 1 , j , target, w + 1) or self.backtracking(grid, i , j + 1, target, w + 1) or self.backtracking(grid, i - 1, j, target, w + 1) or self.backtracking(grid, i, j - 1, target, w + 1)\n",
    "            if res: return True\n",
    "            grid[i][j] = target[w]\n",
    "        return False \n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # def backtraking(grid, target, i, j, w):\n",
    "        #     if w >= len(target): return True\n",
    "        #     if i < 0 or i >= m or j < 0 or j >= n: return False\n",
    "        #     if grid[i][j] == target[w]:\n",
    "        #         grid[i][j] = ''\n",
    "        #         res = backtraking(grid, target, i + 1, j, w + 1) or backtraking(grid, target, i , j + 1, w + 1) or backtraking(grid, target, i - 1, j , w + 1) or backtraking(grid, target, i, j - 1 , w + 1)\n",
    "        #         grid[i][j] = target[w]\n",
    "        #         if res: return res\n",
    "        #     return False \n",
    "        \n",
    "        # m = len(grid)\n",
    "        # n = len(grid[0])\n",
    "        # for i in range(m):\n",
    "        #     for j in range(n):\n",
    "        #         if backtraking(grid, target, i, j, 0): return True\n",
    "        # return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPuzzle(self, grid: List[List[str]], target: str) -> bool:\n",
    "        res = False\n",
    "        k = 0\n",
    "        # 起始元素可以是迷宫矩阵中的任意元素\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                res = res or self.dfs(i , j, k, grid, target)\n",
    "                # 如果已经找到了可行路径，则立即跳出循环\n",
    "                if res: return True\n",
    "        return False\n",
    "\n",
    "    '''\n",
    "    深度优先遍历\n",
    "    @:param i: grid的行索引\n",
    "    @:param j: grid的列索引\n",
    "    @:param k: 目标字符串的索引\n",
    "    @:param grid: 迷宫矩阵\n",
    "    @:param target: 目标字符串\n",
    "    '''\n",
    "    def dfs(self, i, j, k, grid, target):\n",
    "        # 设置递归的终止条件\n",
    "        if not 0 <= i < len(grid) or not 0 <= j < len(grid[0]) or not grid[i][j] == target[k]: return False\n",
    "        if k == len(target)-1: return True\n",
    "        # 递归循环体\n",
    "        # 将grid[i][j]设置为空，标记这个位置已经遍历过了\n",
    "        grid[i][j] = ' '\n",
    "        # 使用or连接是因为在众多路径中只要找到一条可行路径即可\n",
    "        res = (self.dfs(i-1, j, k+1, grid, target) or self.dfs(i+1, j, k+1, grid, target) or\n",
    "                self.dfs(i, j-1, k+1, grid, target) or self.dfs(i, j+1, k+1, grid, target))\n",
    "        # 还原矩阵的元素\n",
    "        grid[i][j] = target[k]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, board, word, i, j, k):\n",
    "        if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or word[k] != board[i][j]:\n",
    "            return False\n",
    "        if k == len(word) - 1:\n",
    "            return True\n",
    "        else:\n",
    "            tmp = board[i][j]\n",
    "            board[i][j] = \"/\"\n",
    "            res = self.dfs(board, word, i, j - 1, k + 1) or self.dfs(board, word, i - 1, j, k + 1) or self.dfs(board, word, i, j + 1, k + 1) or self.dfs(board, word, i + 1, j, k + 1)\n",
    "            board[i][j] = tmp\n",
    "            return res\n",
    "    \n",
    "    def wordPuzzle(self, grid: List[List[str]], target: str) -> bool:\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[i])):\n",
    "                if self.dfs(grid, target, i, j, 0):\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPuzzle(self, grid: List[List[str]], target: str) -> bool:\n",
    "        row, column = len(grid), len(grid[0])\n",
    "        def recur(i, j, grid, dest, target):\n",
    "            row, column = len(grid), len(grid[0])\n",
    "            index = len(dest)\n",
    "            if i < 0 or i >= row or j < 0 or j >= column: return False \n",
    "            if grid[i][j] != target[index]: return False\n",
    "            dest.append(target[index])\n",
    "            if \"\".join(dest) == target: \n",
    "                print(2, dest)\n",
    "                return True\n",
    "            # print(dest, index, row, column, i, j)\n",
    "            memGrid, grid[i][j] = grid[i][j], \"#\"\n",
    "            ret = recur(i + 1, j, grid, dest, target) or \\\n",
    "                recur(i - 1, j, grid, dest, target) or \\\n",
    "                recur(i, j + 1, grid, dest, target) or \\\n",
    "                recur(i, j - 1, grid, dest, target)\n",
    "            dest.pop()\n",
    "            grid[i][j] = memGrid\n",
    "            return ret\n",
    "\n",
    "        for i in range(row):\n",
    "            for j in range(column):\n",
    "                if recur(i, j, grid, [], target): \n",
    "                    print(1)\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPuzzle(self, grid: List[List[str]], target: str) -> bool:\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if self.retrack(grid,target,i,j,0):\n",
    "                    return True\n",
    "        return  False\n",
    "    def retrack(self,grid: List[List[str]], target:str, si: int, sj: int, k) -> bool:\n",
    "        m,n = len(grid), len(grid[0])\n",
    "        if k == len(target):\n",
    "            return True\n",
    "        if not 0<=si<m or not 0<=sj<n or grid[si][sj]!=target[k]:\n",
    "            return False\n",
    "        grid[si][sj] = ''\n",
    "        res = self.retrack(grid,target,si+1,sj,k+1) or \\\n",
    "              self.retrack(grid,target,si-1,sj,k+1) or \\\n",
    "              self.retrack(grid,target,si,sj-1,k+1) or \\\n",
    "              self.retrack(grid,target,si,sj+1,k+1)\n",
    "        grid[si][sj] = target[k]\n",
    "        return  res\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPuzzle(self, grid: List[List[str]], target: str) -> bool:\n",
    "        def helper(grid, target, mark, i, j, rows, columns):\n",
    "            if target == '': return True\n",
    "\n",
    "            if grid[i][j] == target[0] and mark[i][j] == False:\n",
    "                if len(target) == 1:\n",
    "                    return True\n",
    "                mark[i][j] = True\n",
    "                if i - 1 >=0 and helper(grid, target[1:], mark, i-1, j, rows, columns):\n",
    "                    return True\n",
    "                if j - 1 >=0 and helper(grid, target[1:], mark, i, j-1, rows, columns):\n",
    "                    return True\n",
    "                if i + 1 < rows    and helper(grid, target[1:], mark, i+1, j, rows, columns):\n",
    "                    return True\n",
    "                if j + 1 < columns and helper(grid, target[1:], mark, i, j+1, rows, columns):\n",
    "                    return True    \n",
    "                mark[i][j] = False\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "        if target == '': return False\n",
    "\n",
    "        rows = len(grid)\n",
    "        columns = len(grid[0])\n",
    "        for i in range(rows):\n",
    "            for j in range(columns):\n",
    "                mark = [[False for c in range(columns)] for r in range(rows)]\n",
    "                result = helper(grid, target, mark, i, j, rows, columns)\n",
    "                if result == True:\n",
    "                    return True\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPuzzle(self, grid: List[List[str]], target: str) -> bool:\n",
    "        self.m=len(grid)\n",
    "        self.n=len(grid[0])\n",
    "        self.l=len(target)\n",
    "        self.ret=False\n",
    "        self.path=[]\n",
    "        def neighbor(i,j):\n",
    "            dir=[[0,1],[0,-1],[-1,0],[1,0]]\n",
    "            res=[]\n",
    "            for e in dir:\n",
    "                ii,jj=i+e[0], j+e[1]\n",
    "                if ii>=0 and ii<self.m and jj>=0 and jj<self.n:\n",
    "                    res.append([ii,jj])\n",
    "            return res\n",
    "        \n",
    "        def dfs(grid,i,j,k,target):\n",
    "            if (grid[i][j]!=target[k]) or ([i,j] in self.path) or self.ret:\n",
    "                return\n",
    "            \n",
    "            self.path.append([i,j])\n",
    "\n",
    "            if k==self.l-1:\n",
    "                self.ret=True\n",
    "                return\n",
    "            \n",
    "            for e in neighbor(i,j):\n",
    "                ni,nj=e[0],e[1]\n",
    "                # if grid[ni][nj]==target[k+1]:\n",
    "                dfs(grid,ni,nj,k+1,target)\n",
    "            \n",
    "            self.path.pop()\n",
    "\n",
    "\n",
    "        for i in range(self.m):\n",
    "            for j in range(self.n):\n",
    "                # if grid[i][j]!=target[0]:\n",
    "                dfs(grid,i,j,0,target)\n",
    "\n",
    "        return self.ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPuzzle(self, grid: List[List[str]], target: str) -> bool:\n",
    "        def match(g: List[List[str]], target: str, visit: List[List[int]], i: int, j: int) -> bool:\n",
    "            if len(target) == 0:\n",
    "                return True\n",
    "            if i < 0 or i > len(g) - 1:\n",
    "                return False\n",
    "            if j < 0 or j > len(g[0]) - 1:\n",
    "                return False\n",
    "            if g[i][j] != target[0] or visit[i][j] == 1:\n",
    "                return False\n",
    "            visit[i][j] = 1\n",
    "            res = match(g, target[1:], visit, i+1, j) or \\\n",
    "                match(g, target[1:], visit, i-1, j) or \\\n",
    "                match(g, target[1:], visit, i, j+1) or \\\n",
    "                match(g, target[1:], visit, i, j-1)\n",
    "            visit[i][j] = -1\n",
    "            return res\n",
    "        \n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                visit = [[-1]*n for _ in range(m)]\n",
    "                if match(grid, target, visit, i, j):\n",
    "                    return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPuzzle(self, grid: List[List[str]], target: str) -> bool:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        t=0\n",
    "        direct=[(0,1),(0,-1),(-1,0),(1,0)]\n",
    "        visit=[[False]*n for _ in range(m)]\n",
    "\n",
    "        def dfs(grid,x,y):\n",
    "            nonlocal t,direct,m,n,visit,target\n",
    "            if t==len(target):\n",
    "                return True\n",
    "            for i in range(4):\n",
    "                nx=x+direct[i][0]\n",
    "                ny=y+direct[i][1]\n",
    "                if nx<0 or ny<0 or nx>=m or ny>=n or visit[nx][ny] or grid[nx][ny]!=target[t]:\n",
    "                    continue\n",
    "                t+=1\n",
    "                visit[nx][ny]=True\n",
    "                if dfs(grid,nx,ny):\n",
    "                    return True\n",
    "                t-=1\n",
    "                visit[nx][ny]=False\n",
    "            return False\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]!=target[0]:\n",
    "                    continue\n",
    "                else:\n",
    "                    t+=1\n",
    "                    visit[i][j]=True\n",
    "                    if dfs(grid,i,j):\n",
    "                        return True\n",
    "                    t-=1\n",
    "                    visit[i][j]=False\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.move_x = [1,-1,0,0]\n",
    "        self.move_y = [0,0,1,-1]        \n",
    "\n",
    "    def wordPuzzle(self, grid: List[List[str]], target: str) -> bool:\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j]==target[0]:\n",
    "                    tmp = grid[i][j]\n",
    "                    grid[i][j] = '0'\n",
    "                    if self.wordPuzzleUtil(grid,i,j,target[1:]):\n",
    "                        return True\n",
    "                    grid[i][j] = tmp\n",
    "\n",
    "        return False\n",
    "\n",
    "\n",
    "    def isSafe(self,x,y,m,n):\n",
    "        return x >= 0 and y >= 0 and x < m and y < n\n",
    "\n",
    "    def wordPuzzleUtil(self,grid,x,y,target):\n",
    "        if not target:return True\n",
    "        \n",
    "        for i in range(4):\n",
    "            nx = x + self.move_x[i]\n",
    "            ny = y + self.move_y[i]\n",
    "\n",
    "            if self.isSafe(nx,ny,len(grid),len(grid[0])) and grid[nx][ny] == target[0]:\n",
    "                    tmp = grid[nx][ny]\n",
    "                    grid[nx][ny] = '0'\n",
    "                    if self.wordPuzzleUtil(grid,nx,ny,target[1:]):\n",
    "                        return True\n",
    "                    grid[nx][ny] = tmp\n",
    "\n",
    "        return False         \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    dirs = [[0,1],[0,-1],[1,0],[-1,0]]\n",
    "    def wordPuzzle(self, grid: List[List[str]], target: str) -> bool:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        f = [[0]*n for i in range(m)]\n",
    "        def dfs(map,i,j,word):\n",
    "            if len(word) == 0:\n",
    "                return True\n",
    "            for it in self.dirs:\n",
    "                di = i + it[0]\n",
    "                dj = j + it[1]\n",
    "                if 0<= di< len(map) and 0<=dj<len(map[0]) and f[di][dj] == 0 and map[di][dj] == word[0]:\n",
    "                    f[di][dj] = 1\n",
    "                    if dfs(map,di,dj,word[1:]):\n",
    "                        return True\n",
    "                    f[di][dj] = 0\n",
    "            return False \n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == target[0]:\n",
    "                    f[i][j] = 1\n",
    "                    if dfs(grid,i,j,target[1:]):\n",
    "                        return True\n",
    "                    f[i][j] = 0\n",
    "        \n",
    "        return False "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPuzzle(self, grid: List[List[str]], target: str) -> bool:\n",
    "        def dfs(i, j, m, n, grid, target):\n",
    "            # 当前位置 棋盘的界限 棋盘 目标值\n",
    "            if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != target[0]:\n",
    "                # 减枝操作\n",
    "                return False\n",
    "            \n",
    "            if len(target) == 1:  # 存在目标字符串\n",
    "                return True\n",
    "\n",
    "            grid[i][j] = \"1\"  # 修改当前位置的字符，防止重复搜索\n",
    "\n",
    "            # 开始实现递归操作\n",
    "            for k, c in [(0, 1), (0, -1), (1, 0), (-1, 0)]:\n",
    "                if dfs(i + k, j + c, m, n, grid, target[1:]):\n",
    "                    return True\n",
    "            \n",
    "            # 一次dfs失效, 还原字符\n",
    "            grid[i][j] = target[0]\n",
    "\n",
    "            # 未找到\n",
    "            return False\n",
    "\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if dfs(i, j, m, n, grid, target):\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPuzzle(self, grid: List[List[str]], target: str) -> bool:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        def dfs(i, j, idx):\n",
    "            if idx == len(target):\n",
    "                return True\n",
    "            for dx,dy in (1,0),(-1,0),(0,1),(0,-1):\n",
    "                if 0 <= i+dx < m and 0 <= j+dy <n and grid[i+dx][j+dy] == target[idx]:\n",
    "                    grid[i + dx][j + dy] = '/'\n",
    "                    if dfs(i+dx,j+dy,idx+1):\n",
    "                        return True\n",
    "                    grid[i + dx][j + dy] = target[idx]\n",
    "            return False\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == target[0]:\n",
    "                    grid[i][j] = '/'\n",
    "                    if dfs(i,j,1):\n",
    "                        return True\n",
    "                    grid[i][j] = target[0]\n",
    "        return False       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPuzzle(self, grid: List[List[str]], target: str) -> bool:\n",
    "        h = len(grid)\n",
    "        w = len(grid[0])\n",
    "        visited= [[False for i in range(w)] for j in range(h)]\n",
    "\n",
    "        def df(i,j, tar):\n",
    "            if len(tar)==0:\n",
    "                return True\n",
    "            if len(tar)==1:\n",
    "                if grid[i][j]==tar[0]:\n",
    "                    return True\n",
    "            if grid[i][j]!=tar[0]:\n",
    "                return False\n",
    "        \n",
    "            visited[i][j]=True\n",
    "            if i+1<=h-1 and not visited[i+1][j]:\n",
    "                if df(i+1, j, tar[1:]):\n",
    "                    return True\n",
    "                \n",
    "            if j+1<=w-1 and not visited[i][j+1]:\n",
    "                if df(i, j+1, tar[1:]):\n",
    "                    return True\n",
    "\n",
    "            if i-1>=0 and not visited[i-1][j]:\n",
    "                if df(i-1,j,tar[1:]):\n",
    "                    return True\n",
    "\n",
    "            if j-1>=0 and not visited[i][j-1]:\n",
    "                if df(i, j-1, tar[1:]):\n",
    "                    return True\n",
    "            visited[i][j]=False\n",
    "            return False\n",
    "        \n",
    "\n",
    "        for i in range(h):\n",
    "            for j in range(w):\n",
    "                if grid[i][j]==target[0]:\n",
    "                    if df(i,j, target):\n",
    "                        return True\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, i, j, level):\n",
    "        print(i, j, level)\n",
    "        if level == len(self.target): return True\n",
    "        if i < 0 or i == self.m or j <0 or j == self.n: return False\n",
    "        if self.visited[i][j] == 1 or self.grid[i][j] != self.target[level]:\n",
    "            return False\n",
    "\n",
    "        self.visited[i][j] = 1\n",
    "        res = False\n",
    "        if i > 0: res = res or self.dfs(i-1, j, level+1)\n",
    "        if res is False: res = res or self.dfs(i+1, j, level+1)\n",
    "        if res is False: res = res or self.dfs(i, j-1, level+1)\n",
    "        if res is False: res = res or self.dfs(i, j+1, level+1)\n",
    "        self.visited[i][j] = 0\n",
    "        return res\n",
    "    \n",
    "    def wordPuzzle(self, grid: List[List[str]], target: str) -> bool:\n",
    "        self.target = target\n",
    "        self.grid = grid\n",
    "        self.m, self.n = len(grid), len(grid[0])\n",
    "        for i in range(self.m):\n",
    "            for j in range(self.n):\n",
    "                self.visited = [[0 for _ in range(self.n)] for it in range(self.m)]\n",
    "                if self.dfs(i, j, 0): return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPuzzle(self, grid: List[List[str]], target: str) -> bool:\n",
    "        row = len(grid)\n",
    "        col = len(grid[0])\n",
    "        visited = [[0]*col for _ in range(row)]\n",
    "        def match(target, i, j):\n",
    "            if target == \"\":\n",
    "                return True\n",
    "            if i<0 or i>row-1 or j<0 or j>col-1:\n",
    "                return False\n",
    "            if visited[i][j] == 1:\n",
    "                return False\n",
    "            if grid[i][j] != target[0]:\n",
    "                return False\n",
    "            visited[i][j] = 1\n",
    "            res = match(target[1:], i+1, j) or \\\n",
    "                match(target[1:], i, j+1) or \\\n",
    "                match(target[1:], i-1, j) or \\\n",
    "                match(target[1:], i, j-1)\n",
    "            visited[i][j] = 0\n",
    "            return res\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if match(target, i, j):\n",
    "                    return True\n",
    "        return False\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPuzzle(self, grid: List[List[str]], target: str) -> bool:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0]) if grid else 0\n",
    "\n",
    "        def dfs(k, i, j): # k为第k步, i,j为行列\n",
    "            if not 0<=i<m or not 0<=j<n: return False # 越界\n",
    "            if target[k] != grid[i][j]: return False # 不为目标数组中元素\n",
    "            if k == len(target) -1: # 达到指定步数\n",
    "                return True\n",
    "            \n",
    "            # 避免重复使用字母\n",
    "            used = grid[i][j]\n",
    "            grid[i][j] = '#' # 用target中不存在的字符表示已访问过\n",
    "\n",
    "            # 即没有越界，又没有达到指定步数\n",
    "            res = dfs(k+1,i+1,j) or dfs(k+1,i,j+1) or dfs(k+1,i-1,j) or dfs(k+1, i,j-1) # 向四个方向搜索\n",
    "            grid[i][j] = used # 恢复数组中元素\n",
    "            return res\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if dfs(0, i, j):\n",
    "                    return True\n",
    "        return False\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPuzzle(self, grid: List[List[str]], target: str) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        def dfs(i, j, k):\n",
    "            if k == len(target): return True\n",
    "            if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != target[k]: \n",
    "                return False\n",
    "            tmp = grid[i][j]\n",
    "            grid[i][j] = '/'\n",
    "            res = dfs(i - 1, j, k + 1) or dfs(i + 1, j, k + 1) or dfs(i, j - 1, k + 1) or dfs(i, j + 1, k + 1)\n",
    "            grid[i][j] = tmp\n",
    "            return res\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if dfs(i, j, 0): return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPuzzle(self, grid: List[List[str]], target: str) -> bool:\n",
    "        L = len(target)\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        visited = [[0]*n for _ in range(m)]\n",
    "\n",
    "        def dfs(i, x, y):\n",
    "            if i == L: return True\n",
    "            if not (0<=x<m and 0<=y<n): return False\n",
    "            if visited[x][y] or grid[x][y] != target[i]: return False\n",
    "            visited[x][y] = 1\n",
    "            for dx, dy in [[-1, 0], [1, 0], [0, 1], [0, -1]]:\n",
    "                if dfs(i+1, x+dx, y+dy): return True\n",
    "            visited[x][y] = 0\n",
    "            return False\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if dfs(0, i, j): return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPuzzle(self, grid: List[List[str]], target: str) -> bool:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "\n",
    "        def dfs(row,col,index):\n",
    "            if row<0 or row>=m or col<0 or col>=n or grid[row][col]!=target[index]:\n",
    "                return False\n",
    "            if index==len(target)-1:\n",
    "                return True\n",
    "            tmep =grid[row][col]\n",
    "\n",
    "            grid[row][col]=\"*\" #标记已经访问过了\n",
    "\n",
    "            found = dfs(row+1,col,index+1) or dfs(row-1,col,index+1) or  dfs(row,col+1,index+1) or dfs(row,col-1,index+1)\n",
    "            grid[row][col] =tmep\n",
    "            return found\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if dfs(i,j,0):\n",
    "                    return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPuzzle(self, grid: List[List[str]], target: str) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        direction = [[0, 1], [0, -1], [-1, 0], [1, 0]]\n",
    "        visited = [[0] * n for _ in range(m)]\n",
    "\n",
    "        def dfs(x, y, i):\n",
    "            if i == len(target):\n",
    "                return True\n",
    "\n",
    "            flag = False\n",
    "            for dx, dy in direction:\n",
    "                X, Y = x+dx, y+dy\n",
    "                if 0 <= X < m and 0 <= Y < n and not visited[X][Y] and grid[X][Y] == target[i]:\n",
    "                    visited[X][Y] = 1\n",
    "                    flag = dfs(X, Y, i+1)\n",
    "                    visited[X][Y] = 0\n",
    "                    if flag:    return True\n",
    "            return False\n",
    "\n",
    "\n",
    "        flag = False\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == target[0]:\n",
    "                    visited[i][j] = 1\n",
    "                    flag = dfs(i, j, 1)\n",
    "                    visited[i][j] = 0\n",
    "                if flag:    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPuzzle(self, grid: List[List[str]], target: str) -> bool:\n",
    "        rows, cols = len(grid), len(grid[0])\n",
    "        def backtrack(r, c, index):\n",
    "            if index == len(target):\n",
    "                return True\n",
    "            if not 0 <= r < rows or not 0 <= c < cols or grid[r][c] != target[index]:\n",
    "                return False\n",
    "            temp = grid[r][c]\n",
    "            grid[r][c] = '#'\n",
    "            for dr, dc in [(0, 1), (1, 0), (0, -1), (-1, 0)]:\n",
    "                if backtrack(r + dr, c + dc, index + 1):\n",
    "                    return True\n",
    "            grid[r][c] = temp\n",
    "            return False\n",
    "\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                if backtrack(i, j, 0):\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPuzzle(self, grid: List[List[str]], target: str) -> bool:\n",
    "        direction = [[1,0],[0,1],[-1,0],[0,-1]]\n",
    "        m , n = len(grid) , len(grid[0])\n",
    "        visited = [[0] * n for _ in range(m)]\n",
    "        def dfs(x,y,direction,count):\n",
    "            if grid[x][y] != target[count]:\n",
    "                return False\n",
    "            if count == len(target)-1:\n",
    "                return True\n",
    "            visited[x][y] = 1\n",
    "            flag = False\n",
    "            for i in range(4):\n",
    "                next_x = x + direction[i][0]\n",
    "                next_y = y + direction[i][1]\n",
    "                if next_x < 0 or next_x >= m or next_y < 0 or next_y >= n :\n",
    "                    continue\n",
    "                if visited[next_x][next_y] == 1:\n",
    "                    continue\n",
    "                \n",
    "                flag = dfs(next_x,next_y,direction,count+1)\n",
    "                if flag:\n",
    "                    return flag\n",
    "                    break\n",
    "            visited[x][y] = 0\n",
    "            return flag\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if dfs(i,j,direction,0):\n",
    "                    return True\n",
    "        return False\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPuzzle(self, grid: List[List[str]], target: str) -> bool:\n",
    "        def dfs(x, y, idx):\n",
    "            nonlocal res\n",
    "            if not res:\n",
    "                if idx == len(target)-1:\n",
    "                    res = True\n",
    "                    return\n",
    "                for dx, dy in dirs:\n",
    "                    nx = x + dx\n",
    "                    ny = y + dy\n",
    "                    if nx >= 0 and nx < m and ny >= 0 and ny < n and grid[nx][ny] == target[idx+1]:\n",
    "                        tmp = grid[nx][ny]\n",
    "                        grid[nx][ny] = '*'  # marked as visited\n",
    "                        dfs(nx, ny, idx+1)\n",
    "                        grid[nx][ny] = tmp\n",
    "\n",
    "\n",
    "\n",
    "        res = False\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dirs = [(0, 1), (-1, 0), (0, -1), (1, 0)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == target[0]:\n",
    "                    tmp = grid[i][j]\n",
    "                    grid[i][j] = '*'\n",
    "                    dfs(i, j, 0)\n",
    "                    grid[i][j] = tmp\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPuzzle(self, grid: List[List[str]], target: str) -> bool:\n",
    "        def dfs(i,j,k):\n",
    "            if not 0<=i<len(grid) or not 0<=j<len(grid[0]) or grid[i][j] != target[k]:\n",
    "                return False\n",
    "            if k==len(target)-1: return True # 搜索成功\n",
    "            grid[i][j] = ''\n",
    "            res = dfs(i + 1, j, k + 1) or dfs(i - 1, j, k + 1) or dfs(i, j + 1, k + 1) or dfs(i, j - 1, k + 1)\n",
    "            grid[i][j] = target[k]\n",
    "            return res\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if dfs(i,j,0):\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPuzzle(self, grid: List[List[str]], word: str) -> bool:\n",
    "        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "\n",
    "        def exist(i: int, j: int, k: int) -> bool:\n",
    "            if grid[i][j] != word[k]:\n",
    "                return False\n",
    "            if k == len(word) - 1:\n",
    "                return True\n",
    "            \n",
    "            visited.add((i, j))\n",
    "            result = False\n",
    "            for di, dj in directions:\n",
    "                newi, newj = i + di, j + dj\n",
    "                if 0 <= newi < len(grid) and 0 <= newj < len(grid[0]):\n",
    "                    if (newi, newj) not in visited:\n",
    "                        if exist(newi, newj, k + 1):\n",
    "                            result = True\n",
    "                            break\n",
    "            \n",
    "            visited.remove((i, j))\n",
    "            return result\n",
    "\n",
    "        h, w = len(grid), len(grid[0])\n",
    "        visited = set()\n",
    "        for i in range(h):\n",
    "            for j in range(w):\n",
    "                if exist(i, j, 0):\n",
    "                    return True\n",
    "        \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPuzzle(self, grid: List[List[str]], target: str) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        word_len = len(target)\n",
    "        visited = set()\n",
    "\n",
    "        word_counter = defaultdict(int)\n",
    "        for c in target:\n",
    "            word_counter[c] += 1\n",
    "        grid_counter = defaultdict(int)\n",
    "        for l in grid:\n",
    "            for c in l:\n",
    "                grid_counter[c] += 1\n",
    "        for c in word_counter:\n",
    "            if grid_counter[c] < word_counter[c]:\n",
    "                return False\n",
    "        \n",
    "        def dfs(i, j, k):\n",
    "            if grid[i][j] != target[k]:\n",
    "                return False\n",
    "            if k+1 >= word_len:\n",
    "                return True\n",
    "            visited.add((i, j))\n",
    "            for x, y in [[i+1, j], [i-1, j], [i, j+1], [i, j-1]]:\n",
    "                if 0 <= x < m and 0 <= y < n and (x, y) not in visited:\n",
    "                    if dfs(x, y, k+1):\n",
    "                        return True\n",
    "            visited.remove((i, j))\n",
    "\n",
    "        first, last = target[0], target[-1]\n",
    "        if first != last:\n",
    "            count = 0\n",
    "            for c in target:\n",
    "                if c == first:\n",
    "                    count += 1\n",
    "                elif c == last:\n",
    "                    count -= 1\n",
    "            if count > 0:\n",
    "                target = target[::-1]\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if dfs(i, j, 0):\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPuzzle(self, grid: List[List[str]], target: str) -> bool:\n",
    "        visited = set()\n",
    "        m, n, target_length = len(grid), len(grid[0]), len(target)\n",
    "        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n",
    "        def dfs(x, y, k):\n",
    "            if not 0 <= x < m or not 0 <= y < n or not 0 <= k < target_length: return False\n",
    "            if (x, y) in visited: return False\n",
    "            if grid[x][y] != target[k]: return False \n",
    "            if k == target_length - 1: return True\n",
    "\n",
    "            # grid[x][y] = ''\n",
    "            visited.add((x, y))\n",
    "            res = dfs(x+1, y, k+1) or dfs(x-1, y, k+1) or dfs(x, y+1, k+1) or dfs(x, y-1, k+1)\n",
    "            # grid[x][y] = target[k]\n",
    "            visited.remove((x, y))\n",
    "            \n",
    "            return res \n",
    "            \n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if dfs(i, j, 0): return True\n",
    "        return False "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPuzzle(self, grid: List[List[str]], target: str) -> bool:\n",
    "        row, column = len(grid), len(grid[0])\n",
    "        def recur(i, j, k):\n",
    "            row, column = len(grid), len(grid[0])\n",
    "            if i < 0 or i >= row or j < 0 or j >= column: return False \n",
    "            if grid[i][j] != target[k]: return False\n",
    "            if k == len(target) - 1: return True\n",
    "            grid[i][j] = \" \"\n",
    "            ret = recur(i + 1, j, k + 1) or \\\n",
    "                recur(i - 1, j, k + 1) or \\\n",
    "                recur(i, j + 1, k + 1) or \\\n",
    "                recur(i, j - 1, k + 1)\n",
    "            grid[i][j] = target[k]\n",
    "            return ret\n",
    "\n",
    "        for i in range(row):\n",
    "            for j in range(column):\n",
    "                if recur(i, j, 0): \n",
    "                    return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPuzzle(self, grid: List[List[str]], target: str) -> bool:\n",
    "        def recur(k,i,j):\n",
    "            if not 0<=i<len(grid) or not 0<=j<len(grid[0]) or grid[i][j]!=target[k]:\n",
    "                return False\n",
    "            if k==len(target)-1: return True\n",
    "            grid[i][j]=''\n",
    "            res=recur(k+1,i-1,j) or recur(k+1,i+1,j) or recur(k+1,i,j-1) or recur(k+1,i,j+1)\n",
    "            grid[i][j]=target[k]\n",
    "            return res\n",
    "\n",
    "        for a in range(len(grid)):\n",
    "            for b in range(len(grid[0])):\n",
    "                if recur(0,a,b): \n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPuzzle(self, grid: List[List[str]], target: str) -> bool:\n",
    "        # 思路：\n",
    "        # 1.遍历整个board,找到word字符串第一个单词匹配的单词\n",
    "        # 2.找到单词后，我们将调用search函数遍历每种可能的组合（上，下，左，右）\n",
    "        # 3.如果该函数返回true，则 字符串存在\n",
    "        # 4.否者继续检查，直到退出循环为止。\n",
    "        row = len(grid)\n",
    "        col = len(grid[0])\n",
    "        first_char = target[0]\n",
    "        result = False\n",
    "    \n",
    "        def backTracking(wordIndex, i, j,):\n",
    "            # Ending 1: ❌ 越界或单词不匹配\n",
    "            if (not 0<=i<row) or (not 0<=j<col) or grid[i][j] != target[wordIndex]:\n",
    "                return False\n",
    "\n",
    "            # Ending 2: ✅ 最后一位匹配，即单词完全匹配\n",
    "            if wordIndex == len(target)-1:\n",
    "                return True\n",
    "            \n",
    "            # BackTracking, 匹配上\n",
    "            grid[i][j] = '' # 抹掉，防止再次回来\n",
    "            result = backTracking(wordIndex+1, i+1,j) or \\\n",
    "                     backTracking(wordIndex+1, i,j+1) or \\\n",
    "                     backTracking(wordIndex+1, i-1,j) or \\\n",
    "                     backTracking(wordIndex+1, i,j-1)\n",
    "            grid[i][j] = target[wordIndex]  # 复原\n",
    "            return result\n",
    "            \n",
    "\n",
    "        # 1.遍历整个board,找到word字符串第一个单词匹配的单词\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if first_char == grid[i][j]:\n",
    "                    result = backTracking(0, i, j)\n",
    "                    # 如果找到结果，立即返回即可。后序不一定为True，虽然可能有多条路径。\n",
    "                    if result == True: \n",
    "                        return True\n",
    "        return result\n",
    "                "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
